package 程序员面试金典;

import java.util.HashSet;
import java.util.Set;

/**
 * 面试题 08.08. 有重复字符串的排列组合
 * 有重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合。
 *
 * 示例1:
 *
 *  输入：S = "qqe"
 *  输出：["eqq","qeq","qqe"]
 * 示例2:
 *
 *  输入：S = "ab"
 *  输出：["ab", "ba"]
 * 提示:
 *
 * 字符都是英文字母。
 * 字符串长度在[1, 9]之间。
 */
public class T08_08 {
    private boolean[] used = new boolean[10];
    private Set<String> ans = new HashSet<>(); //使用set去重
    private StringBuilder builder = new StringBuilder();

    public String[] permutation(String S) {

        dfs(S);
        String[] result = new String[ans.size()];

        return ans.toArray(result);

    }

    public void dfs(String S) {
        if (builder.length() == S.length()) {
            ans.add(builder.toString());
            return;
        }

        for (int i = 0; i < S.length(); i++) {

            if (!used[i]) {
                char c = S.charAt(i);
                builder.append(c);
                used[i] = true;
                dfs(S);
                builder.deleteCharAt(builder.length() - 1);
                used[i] = false;
            }
        }

    }

}
